#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

class Hermite
{
private:
    int n;
    vector<double> x;
    vector<vector<double>> y;
    vector<vector<double>> table;
public:
    Hermite();
    Hermite(vector<double> x1, vector<vector<double>> y1)
    {
        for (int i = 0;i < x1.size();i++)
        {
            for (int j = 0;j < 2;j++)
            {
                x.push_back(x1[i]);
            }
        }
        n = y1.size() * y1[0].size();
        y = y1;
        table = diff();
    }
    vector<vector<double>> diff()
    {
        vector<vector<double>> Int(n);
        for (int i = 0;i < n;i++)
        {
            Int[i].resize(n);
        }
        for (int j = 0;j < n;j++)
        {
            int k = 0;
            for (int i = 0;i < n;i++)
            {
                if (j == 0)
                {
                    if (i < y.size())
                        Int[i][j] = y[i][j];
                }
                else if (i + j < n)
                {
                    if (x[i] == x[i + j])
                    {
                        Int[i][j] = y[k][j];
                        k++;
                    }
                    else
                    {
                        Int[i][j] = (Int[i - k][j - 1] - Int[i - k + 1][j - 1]) / (x[i] - x[i + j]);
                    }
                }
            }
        }
        return Int;
    }

    void output()
    {
        cout << "     The resulting polynomial is";
        for (int i = 0;i < y.capacity() * y[0].capacity();i++)
        {
            if (table[0][i] != 0)
            {
                if (abs(table[0][i]) != 1)
                {
                    cout << abs(table[0][i]);
                    if (i != 0)
                        cout << "*";
                }
                for (int j = 0;j < i;j++)
                {
                    if (x[j] < 0)
                    {
                        cout << "(x+" << -x[j] << ")";
                    }
                    else if (x[j] == 0)
                    {
                        cout << "x";
                    }
                    else
                    {
                        cout << "(x-" << x[j] << ")";
                    }
                    if (j < (i - 1))
                        cout << "*";
                }
                if (i < (y.capacity() * y[0].capacity() - 1))
                {
                    if (table[0][i + 1] >= 0)
                        cout << "+";
                    else
                        cout << "-";
                }
            }
        }
    }
    double getTable(int i, int j)
    {
        return table[i][j];
    }
    double getX(int i)
    {
        return x[i];
    }
};



